#include<list>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
//#include<gecode/driver.hh>
//#include<gecode/int.hh>

using namespace std;

class Word{ 
    public:
	int x,y;
	bool oriz;
	int l;
	
	Word(int x,int y,bool z,int l):
	    x(x),y(y),oriz(z),l(l) {};
	
	bool isOriz(){
	    return oriz;
	    };
	    
	int getLenght(){
	    return l;
	    };    
};

//classe contenitore per la conversione
// lista contiene ogni parola di lunghezza l, e il numero di tali parole 
class Word_set{
public:
    int l_words;
    int num_words;
    std::list<Word*> set;
    
    Word_set(int l=0):l_words(l),num_words(0){};
   
    void addWord(Word* a){
	set.push_back(a);
	num_words++;
    };
    
    void setLenghts(int k){l_words=k;};
	    
};

class Generatore{

private:
    const int width;
    const int height;
    const int blk_case;
    bool* case_b;	//true => casella nera
    
public:
    int tot_w;
    
    int mx(int x, int y){
	return y*width +x;	
    };
    
    int getX(int r){return r%width;}
    
    int getY(int r){return r/width;}
    
    Generatore(int w_p=0,int h_p=0, int blk_p=0):
	    width(w_p),height(h_p),blk_case(blk_p),tot_w(0){
		case_b = new bool[width*height];
	};
    
    bool select(int x,int y){
		//controlla anche i bordi(= true)
		if(x<0 || x>= width || y<0 || y>= height)
		    return true;
		else
		    return case_b[mx(x,y)];	
    };
    
    //posizione causale delle caselle nere 
    void blackCaseGen(){
		srand(time(0));
		int blk=blk_case;
		while(blk!=0){
			int r= rand() % (width*height); //numero random tra 0 e w*h
			//se gia presente una casella nera j--
			//cout<<r<<endl;
			if (case_b[r]!=true && !check_one(r)) 
			//controllo che l'eventuale inserimento della casella nera non generi parole di 1 sola casella
			//setto la casella a nera
			{
			blk--;
			case_b[r]=true;
			}
		}
	
    };
    
    //OK
    bool check_one(int r){
			//controllo che ogni casella bianca abbia almento una casella bianca adiacente
			case_b[r]=true; //provo a settare la casella a nera
			bool find=false;
			for(int y=0;y<height;y++)
				for (int x=0; x< width;x++)
				if (select(x,y)!=true){
				//sono in una casella bianca
					//uso select anche per i bordi
					if (select(x-1,y) && select(x+1,y) && select(x,y+1) && select(x,y-1) ){
						find= true;
						cout<<"singola"<<endl;
					}
				}
			case_b[r]=false; //ripristino	
			return find;
	
    }
    
	std::list<Word*> findWords(){
		std::list<Word*> list_w;
		
		bool magg22=false;
		//cerco orizzontali
		for(int y1=0; y1<height; y1++){
			int l_w=0;
			int x_init=0;
			int y_init= y1;
			bool oriz=true;
			
			for(int x1=0; x1<=width; x1++){
			//cout<<x1+y1*width<<endl;
			if (select(x1,y1)!=true){	//trovo una casella nera
				l_w++;
			}
			else{
				if(l_w >= 2){ //aggiungo la parola solo se è più grande di 2 lettere
					list_w.push_back( new Word(x_init,y_init,oriz,l_w) ); //infili la parola nella lista
					if (l_w>22) magg22=true;
					tot_w++; //aggiorno contatore parole totali
					//cout<< tot_w<< " Oriz ("<<x_init<<","<<y_init<<") lunga "<<l_w<<endl;
				}
				l_w=0; //azzero contatore lunghezza
				x_init= x1+1; //una nuova parola può iniziare alla casella successiva
				}
	    	}	    
		}
		//fine orizzontali 
	
		//cerco verticali
		for(int x1=0; x1<width; x1++){
			int l_w=0;
			int x_init=x1;
			int y_init= 0;
			bool oriz=false;
			
			for(int y1=0; y1<=height; y1++){
			//cout<<x1+y1*width<<endl;
			if (select(x1,y1)!=true){	//trovo una casella nera
				l_w++;
			}
			else{
				if(l_w >= 2){ //aggiungo la parola solo se è più grande di 2 lettere
					list_w.push_back( new Word(x_init,y_init,oriz,l_w) ); //infili la parola nella lista
					if (l_w>22) magg22=true;
					tot_w++; //aggiorno contatore parole totali
					//cout<< tot_w<< " Vert ("<<x_init<<","<<y_init<<") lunga "<<l_w<<endl;
					}
				l_w=0; //azzero contatore lunghezza
				y_init= y1+1; //una nuova parola può iniziare alla casella successiva
				}
			}    
	    
		}
		//fine verticali
	
		if(magg22==false)
			cout<< "parola x 22 "<<endl;
		else
			cout<< "parola > 22 "<<endl;

		return list_w;
	
    }
    
   
    int* genera(){
		//aggiungo le caselle nere random alla griglia
		blackCaseGen();
	
		print_grid();
		cout<<"trovo parole"<<endl;
		//trovo e ritorno le parole nella griglia
		std::list<Word*> k= findWords();
		cout<<"parole totali=" <<tot_w<<endl<<"conversione"<<endl;
		tot_w=0; //resetto contatore parole
		return convertitore(k);
    }
    
    void print_grid(){
		int nere=0;
		for(int j=0;j<height;j++){
			cout <<""<<endl;
			for (int k=0; k< width;k++){
			cout <<(select(k,j));
			if (select(k,j))
				nere++;
			}
		};
		cout<<endl<<"nere = "<<nere<<endl;
		
   };
   
   std::list<int> blkCoord(){
       std::list<int> nere;
       int count=0;
       for (int i=0;i<width*height;i++)
	   if(case_b[i]==true){
	       count++;
	       nere.push_back(getX(i));
	       nere.push_back(getY(i));
	   }
	       
	       
	if(count!=blk_case) cout<<"errore n caselle nere"<<endl;
	
	return nere;
    
       
};
   
   int* convertitore(std::list<Word*> lista_w){
       
       
       //conteggio elementi array
       int elem =3; //width,height,#blkcase
       //conteggio coordinate blackcase
       elem+= blk_case*2; // blk (x,y)
       
       //divido le parole in set in base alla lunghezza
       std::list<Word*> aux=lista_w;
       
       const int max_l=22;
       Word_set parole[max_l];	//non ci sono parole più lunghe di 22 caratteri
       for(int i=0;i<max_l;i++) //inizializzo array
	   parole[i].setLenghts(i);
       
       while(!aux.empty()){
	    Word* tmp_w = aux.front();
	    aux.pop_front();
	    parole[tmp_w->getLenght()].addWord(tmp_w);
	}
	
	//conteggio parole per lunghezza
	int p_set=0;
	for(int i=0;i<max_l;i++) //inizializzo array
	   if(parole[i].num_words != 0)
	       p_set+= 2 + 3*parole[i].num_words; // lunghezza l ,#parole lunghe l , coordinate parole(x,y,dir)
	
       elem += (p_set + 1); // +1 è marker
       
       cout<<" num elementi ="<<elem<<" "<<p_set<<endl;
       
       const int e=elem;
       int* g;
       g = (int *) malloc(e * sizeof(int)); //alloco un array di e elementi
       
       //inizio a riempire il mio array
       g[0]= width;
       g[1]=height;
       g[2]=blk_case;
       int counter=3;
       std::list<int> blk_c = blkCoord();
       //inserisco nell'array le coordinate delle caselle nere
       while(!blk_c.empty()){
	   g[counter++]=blk_c.front();
	   blk_c.pop_front();
	}
	
	Word* aux1;
	for(int i=0; i<max_l;i++){
	    if(parole[i].num_words != 0){
		int num=parole[i].num_words;
		g[counter++]=parole[i].l_words;
		g[counter++]=num;
		for(int k=0; k<num;k++){
		   aux1= (parole[i].set).front();
		   parole[i].set.pop_front();
		   g[counter++]=aux1->x;
		   g[counter++]=aux1->y;
		   g[counter++]= (aux1->isOriz()) ? 0 : 1;
		}
		    
		
	    }
	}
	
	g[counter++]=0;
	
	if(counter==elem) cout<<"tutto ok"<<endl;
	
	/*for(int i=0;i<counter;i++)
	    cout<<g[i]<<",";
	  */ 
    
    return g;

    };

    
};

/*
int main(){
    Generatore* g= new Generatore(10,10,60); //(parola più lunga = 22)
    
    g->genera();
    return 0;
};
*/
